package com.example.study2;

import java.util.Arrays;

/**
 * 自定义顺序表实现类
 * 基于动态数组实现，支持自动扩容和缩容
 */
public class MyArrayList implements IList {
    // 底层存储数组 - 用于实际存储顺序表的元素
    public int[] elem;
    // 有效数据个数 - 记录当前顺序表中实际存储的元素数量
    public int usedSize;

    /**
     * 默认构造方法
     * 初始化容量为10的数组
     * 时间复杂度：O(1)
     */
    public MyArrayList() {
        this.elem = new int[10];  // 初始分配10个元素的数组空间
        this.usedSize = 0;        // 初始时没有元素，有效个数为0
    }

    /**
     * 带初始容量的构造方法
     * @param capacity 初始容量
     * 时间复杂度：O(1)
     */
    public MyArrayList(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("容量必须大于0");
        }
        this.elem = new int[capacity];
        this.usedSize = 0;
    }

    /**
     * 在顺序表末尾添加元素
     * @param data 要添加的元素值
     * 把data放在数组中 有效数据的最后一个位置，满时扩容。
     * 平均时间复杂度：O(1)（分摊分析）
     * 最坏时间复杂度：O(n)（需要扩容时）
     */
    @Override
    public void add(int data) {
        // 检查数组是否已满，如果已满需要进行扩容
        if (isFull()) {
            grow();  // 调用扩容方法
        }
        // 在数组的末尾位置插入新元素
        elem[usedSize] = data;
        // 有效元素个数加1
        usedSize++;
    }

    /**
     * 动态扩容方法
     * 当数组已满时，创建原来1.5倍大小的新数组并复制数据
     * 时间复杂度：O(n)
     */
    private void grow() {
        // Arrays.copyOf会创建新数组并自动复制原数组内容
        // 新容量 = 原容量 * 1.5，这样设计是为了平衡内存使用和扩容频率
        elem = Arrays.copyOf(elem, elem.length * 3 / 2 + 1);
    }

    /**
     * 判断顺序表是否已满
     * @return true-已满, false-未满
     * 时间复杂度：O(1)
     */
    @Override
    public boolean isFull() {
        // 当有效元素个数等于数组长度时，说明数组已满
        return usedSize == elem.length;
    }

    /**
     * 在指定位置插入元素
     * @param pos 插入位置（0-based索引）
     * @param data 要插入的元素值
     * 时间复杂度：O(n)
     * @throws PosOutOfException 当位置不合法时抛出异常
     */
    @Override
    public void add(int pos, int data) {
        // 参数校验：插入位置必须在[0, usedSize]范围内
        // 允许在usedSize位置插入，相当于在末尾添加
        if (pos < 0 || pos > usedSize) {
            throw new PosOutOfException("位置 " + pos + " 越界，有效范围[0, " + usedSize + "]");
        }

        // 检查是否需要扩容
        if (isFull()) {
            grow();
        }

        // 数据搬移：从后向前将pos位置及之后的元素向后移动一位
        // 为新的元素腾出位置
        for (int i = usedSize - 1; i >= pos; i--) {
            elem[i + 1] = elem[i];  // 将元素向后移动
        }

        // 在腾出的pos位置插入新元素
        elem[pos] = data;
        // 更新有效元素个数
        usedSize++;
    }

    /**
     * 判断顺序表是否包含指定元素
     * @param toFind 要查找的元素值
     * @return true-包含, false-不包含
     * 时间复杂度：O(n)
     */
    @Override
    public boolean contains(int toFind) {
        // 遍历数组，逐个比较元素
        for (int i = 0; i < usedSize; i++) {
            if (elem[i] == toFind) {
                return true;  // 找到目标元素
            }
        }
        return false;  // 遍历完成未找到
    }

    /**
     * 查找元素第一次出现的位置
     * @param toFind 要查找的元素值
     * @return 元素索引，未找到返回-1
     * 时间复杂度：O(n)
     */
    @Override
    public int indexOf(int toFind) {
        // 线性查找：从前往后遍历数组
        for (int i = 0; i < usedSize; i++) {
            if (elem[i] == toFind) {
                return i;  // 返回元素索引
            }
        }
        return -1;  // 特殊值-1表示未找到
    }

    /**
     * 获取指定位置的元素
     * @param pos 元素位置（0-based索引）
     * @return 该位置的元素值
     * 时间复杂度：O(1)
     * @throws PosOutOfException 当位置不合法时抛出异常
     */
    @Override
    public int get(int pos) {
        // 参数校验：位置必须在[0, usedSize-1]范围内
        if (pos < 0 || pos >= usedSize) {
            throw new PosOutOfException("位置 " + pos + " 越界，有效范围[0, " + (usedSize - 1) + "]");
        }
        // 直接通过索引访问数组元素，这是顺序表的优势
        return elem[pos];
    }

    /**
     * 修改指定位置的元素值
     * @param pos 要修改的位置
     * @param value 新的元素值
     * 时间复杂度：O(1)
     * @throws PosOutOfException 当位置不合法时抛出异常
     */
    @Override
    public void set(int pos, int value) {
        // 参数校验
        if (pos < 0 || pos >= usedSize) {
            throw new PosOutOfException("set方法中pos位置不合法");
        }
        // 直接通过索引修改数组元素
        elem[pos] = value;
    }

    /**
     * 删除第一次出现的指定元素
     * @param toRemove 要删除的元素值
     * 时间复杂度：O(n)
     */
    @Override
    public void remove(int toRemove) {
        // 先查找要删除元素的位置
        int index = indexOf(toRemove);
        // 如果元素不存在，直接返回
        if (index == -1) {
            return;
        }

        // 数据搬移：从删除位置开始，将后续元素向前移动一位
        // 覆盖要删除的元素
        for (int i = index; i < usedSize - 1; i++) {
            elem[i] = elem[i + 1];  // 前移覆盖
        }

        // 更新有效元素个数
        usedSize--;
        // 检查是否需要缩容以节省内存
        shrink();
    }

    /**
     * 删除顺序表中所有等于指定值的元素
     * @param toRemove 要删除的元素值
     * 时间复杂度：O(n)
     */
    @Override
    public void removeAll(int toRemove) {
        // 使用双指针法：j指向新数组中应保留元素的位置
        int j = 0;
        for (int i = 0; i < usedSize; i++) {
            // 如果当前元素不是要删除的元素，则保留
            if (elem[i] != toRemove) {
                elem[j] = elem[i];  // 将元素移动到j位置
                j++;                // j指针后移
            }
            // 如果要删除的元素，则跳过（不复制）
        }
        // 更新有效元素个数（j就是删除后的元素个数）
        usedSize = j;
        // 检查是否需要缩容
        shrink();
    }

    /**
     * 动态缩容方法
     * 当有效数据不足容量一半且容量大于10时进行缩容
     * 时间复杂度：O(n)
     */
    private void shrink() {
        // 缩容条件：有效元素不到容量的一半，且当前容量大于10
        // 避免频繁缩容和容量过小
        if (usedSize * 2 < elem.length && elem.length > 10) {
            // 新容量取当前容量的一半和10中的较大值
            int newCapacity = Math.max(10, elem.length / 2);
            elem = Arrays.copyOf(elem, newCapacity);
        }
    }

    /**
     * 获取顺序表当前元素个数
     * @return 元素个数
     * 时间复杂度：O(1)
     */
    @Override
    public int size() {
        return usedSize;
    }

    /**
     * 清空顺序表
     * 时间复杂度：O(1)
     */
    @Override
    public void clear() {
        // 如果存储的是引用类型，需要遍历置为null避免内存泄漏
        // for (int i = 0; i < usedSize; i++) {
        //     elem[i] = null;
        // }

        // 对于基本类型int，直接重置usedSize即可
        // 后续操作会覆盖原有数据
        usedSize = 0;

        // 可选：缩容到初始大小以节省内存
        if (elem.length > 10) {
            elem = new int[10];
        }
    }

    /**
     * 打印顺序表内容（用于调试和测试）
     * 时间复杂度：O(n)
     */
    @Override
    public void display() {
        // 遍历所有有效元素并打印
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();  // 换行
    }
}